import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

class Solution {
    public int minMutation(String startGene, String endGene, String[] bank) {
        int ret = 0;
        Set<String> set1 = new HashSet<>();
        for(String s : bank){
            set1.add(s);
        }
        Set<String> set2 = new HashSet<>();
        char[] ch = {'A', 'C', 'G', 'T'};
        Queue<String> queue = new LinkedList<>();
        queue.offer(startGene);
        set2.add(startGene);
        while(!queue.isEmpty()){
            int size = queue.size();
            ret++;
            while(size > 0){
                String s = queue.poll();
                // 穷举所有字符串
                for(int i = 0; i < 8; i++){
                    for(char c : ch){
                        char[] sArr = s.toCharArray();
                        sArr[i] = c;
                        String tmp = new String(sArr);
                        if(set1.contains(tmp) && !set2.contains(tmp)){
                            queue.offer(tmp);
                            set2.add(tmp);
                            if(tmp.equals(endGene)){
                                return ret;
                            }
                        }
                    }
                }
                size--;
            }
        }
        return -1;
    }
}